package com.gxc.array;

/**
 * 有一些排成一行的正方形。
 * 每个正方形已经被染成红色或者绿色。
 * 现在可以选择任意一个正方形,然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。
 * 目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。
 * 想知道他最少需要涂染几个正方形。
 * 如样例所示:
 *      s=RGRGR
 * 我们涂染之后变成
 *      RRRGG
 * 满足要求了,涂染的个数为2,没有比这个更好的涂染方案
 */
public class Dye {

    public static void main(String[] args) {
        String s = "GRGRGRR";
        char[] chars = s.toCharArray();
        int[] G = left(chars);
        for (int i = 0; i < G.length; i++) {
            System.out.print(G[i] + " ");
        }
        System.out.println("");
        int[] R = right(chars);
        for (int i = 0; i < R.length; i++) {
            System.out.print(R[i] + " ");
        }

        //i位置上的字符不变，i左侧有多少G需要变成R,i右侧有多少R需要变成G,两个数量汇总就是i位置不变情况下，达成目标的步数
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < chars.length; i++) {
            if (i==0) {
                min = Math.min(min, R[i]);
            } else if (i == chars.length-1) {
                min = Math.min(min, G[i]);
            } else {
                min = Math.min(min, R[i] + G[i]);
            }
        }
        System.out.println("---------");
        System.out.println(min);
    }

    /**
     * 字符本身及左侧有多少个G（如果都变成R的代价）
     * @param chars
     * @return
     */
    private static int[] left(char[] chars) {
        int[] g = new int[chars.length];
        int n = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'G') {
                n++;
            }
            g[i] = n;
        }
        return g;
    }


    /**
     * 字符本身及右侧有多少个R（如果都变成G的代价）
     * @param chars
     * @return
     */
    private static int[] right(char[] chars) {
        int[] r = new int[chars.length];
        int n = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == 'R') {
                n++;
            }
            r[i] = n;
        }
        return r;
    }
}
